﻿# 算法性能评估

# 【时间复杂度】
    # 规模：数据的大小对我们的算法至关重要
    # 测试环境：环境的快慢对算法至关重要

# 大O表示法
def tmp(n):
    add = 0
    for i in range(n):
        add += i
    return n

    # 算法运行时间T(n) = (2n+1) * unit
    # 算法的运行时间与数据规模成正比：T(n) = O(f(n)),大O表示T(n)与f(n)成正比
    # 大O表示渐进时间复杂度
    # 表示代码执行时间随数据规模增长的变化趋势

# 只关注循环次数多的代码
    # 把n想象成无限大的数据，代码规模也会变得非常大，低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略
    # 所以方法tmp可取时间复杂度：O(n)

# 选大量级
def tmp1(n):
    for i in range(999):
        print(123)
    for i in range(n):
        print(1)
    for i in range(n):
        for j in range(n):
            print(2)

    # 复杂度O(n2)

# 嵌套循环要乘积
def tmp2(n):
    for i in range(n):
        print(123)
def tmp3(n):
    for i in range(n):
        tmp2(i)

    # 复杂度O(n2)

"""
常见复杂度分析
非多项式量级（过于低效） : O(2n) 和 O(n!)。

多项式量级:O(1), O(logn), O(n), O(nlogn), O(nk)

O(1)
a=2
b=3
d=4
...

-----------------------------------------------

O(logn)
def tmp(n):
    i = 1
    while i < n :
        i = i * 2
i = 20,21, 22, 23…2x

退出循环的条件是 : 2x = n ,即 x = log2n，时间复杂度为 Ｏ(log2n)

-----------------------------------------------

def tmp(n):
    i = 1
    while i < n :
        i = i * 3
log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。
基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于 O(log3n)。
因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)
-----------------------------------------------
O(m+n)、O(m*n)

def tmp(m, n):
    for i in range(m):
        print(1)

    for i in range(n):
        print(2)


"""

# 【空间复杂度】
    # 空间复杂度是存储空间与数据规模之间的增长关系
"""
空间复杂度
    渐进时间复杂度：表示算法的执行时间与数据规模之间的增长关系。
    渐进空间复杂度：表示算法的存储空间与数据规模之间的增长关系。

def tmp(n):
    a = [1]*n
    for i in a:
        print(i)
空间复杂度是： O(n)

"""
